// https://www.lintcode.com/problem/majority-number-iii/

public class Solution {
    /**
     * @param nums: A list of integers
     * @param k: An integer
     * @return: The majority number
     */
    public int majorityNumber(List<Integer> nums, int k) {
        // write your code here
        // 参考majority-element-ii扩展一下，空间复杂度的限制是关键。
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer i : nums) {
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else if (map.size() < k) { // 限制空间复杂度
                map.put(i, 1);
            } else { // 踢人！
                List<Integer> keysToDelete = new ArrayList<>();
                for (Integer key : map.keySet()) {
                    map.put(key, map.get(key) - 1);
                    if (map.get(key) == 0) {
                        keysToDelete.add(key);
                    }
                }
                for (Integer key : keysToDelete) {
                    map.remove(key);
                }
            }
        }
        int ret = 0;
        int mc = 0;
        for (Integer i : nums) {
            if (map.containsKey(i)) {
                if (map.get(i) > mc) {
                    mc = map.get(i);
                    ret = i;
                }
            }
        }
        return ret;
    }
}